package java学习.算法.二叉树;

import java.util.HashMap;
import java.util.HashSet;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/11 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 在二叉树中找到两个节点的最近公共祖先 {


    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 使用 map存放：<节点，父节点>
        // 将o1的 所有 父节点放入Set
//        遍历Set 是否有o2，没有就继续 往上找父节点
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(root.val,null);
        InsertNodeInmap(map,root);
        HashSet<Integer> set = new HashSet<>();
//        while (map.get(o1)!=null){
//            int node = map.get(o1);
//            set.add(node);
//            o1 = node;
//        }
        Integer integer = map.get(o1);
        while ( integer!=null){
            set.add(integer);
            integer = map.get(integer);
        }
        Integer parent = map.get(o2);
        while (!set.contains( parent )){
            parent = map.get(parent);
        }

        return parent;

    }

    private void InsertNodeInmap(HashMap<Integer, Integer> map, TreeNode root) {
        if (root.left!=null){
            map.put(root.left.val,root.val);
            InsertNodeInmap(map,root.left);
        }
        if (root.right!=null){
            map.put(root.right.val,root.val);
            InsertNodeInmap(map,root.right);
        }
    }

    TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if (root==null){
           return null;
       }
       if (p==root||q==root){
           return root;
       }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.left, p, q);


        if (left==null&&right==null){
            return null;
        }
        if (left==null||right==null){
            return left==null?right:left;
        }
        return root;
    }
    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        return CommonAncestor(root, o1, o2).val;
    }

    public TreeNode CommonAncestor (TreeNode root, int o1, int o2) {
        if (root == null || root.val == o1 || root.val == o2) { // 如果root为空，或者root为o1、o2中的一个，则它们的最近公共祖先就为root
            return root;
        }

        TreeNode left = CommonAncestor(root.left,o1,o2);    // 递归遍历左子树，只要在左子树中找到了o1或o2，则先找到谁就返回谁
        TreeNode right = CommonAncestor(root.right,o1,o2);  // 递归遍历右子树，只要在右子树中找到了o1或o2，则先找到谁就返回谁
        if (left == null) {  // 如果在左子树中o1和o2都找不到，则o1和o2一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
            return right;
        }else if (right == null) { // 否则，如果left不为空，在左子树中有找到节点（o1或o2），这时候要再判断一下右子树中的情况，
            // 如果在右子树中，o1和o2都找不到，则 o1和o2一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
            return left;
        }else{
            return root; // 否则，当 left和 right均不为空时，说明 o1、o2节点分别在 root异侧, 最近公共祖先即为 root
        }
    }
}
